home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / DJLSR106.ARJ / BITSET.CC < prev    next >
C/C++ Source or Header  |  1992-03-30  |  20KB  |  965 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitSet class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation "BitSet.h"
  24. #endif
  25. #include <BitSet.h>
  26. #include <std.h>
  27. #include <values.h>
  28. #include <_Obstack.h>
  29. #include <AllocRing.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32. #include <string.h>
  33.  
  34. void BitSet::error(const char* msg) const
  35. {
  36.   (*lib_error_handler)("BitSet", msg);
  37. }
  38.  
  39. //  globals & constants
  40.  
  41. BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here
  42.  
  43. #define ONES               ((unsigned short)(~0L))
  44. #define MAXBitSetRep_SIZE  ((1 << (SHORTBITS - 1)) - 1)
  45. #define MINBitSetRep_SIZE  16
  46.  
  47. #ifndef MALLOC_MIN_OVERHEAD
  48. #define MALLOC_MIN_OVERHEAD     4
  49. #endif
  50.  
  51. // break things up into .s indices and positions
  52.  
  53.  
  54. // mask out bits from left
  55.  
  56. static inline unsigned short lmask(int p)
  57. {
  58.   return ONES << p;
  59. }
  60.  
  61. // mask out high bits
  62.  
  63. static inline unsigned short rmask(int p)
  64. {
  65.   return ONES >> (BITSETBITS - 1 - p);
  66. }
  67.  
  68.  
  69. inline static BitSetRep* BSnew(int newlen)
  70. {
  71.   unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) 
  72.     + MALLOC_MIN_OVERHEAD;
  73.   unsigned int allocsiz = MINBitSetRep_SIZE;;
  74.   while (allocsiz < siz) allocsiz <<= 1;
  75.   allocsiz -= MALLOC_MIN_OVERHEAD;
  76.   if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short))
  77.     (*lib_error_handler)("BitSet", "Requested length out of range");
  78.     
  79.   BitSetRep* rep = (BitSetRep *) new char[allocsiz];
  80.   bzero(rep, allocsiz);
  81.   rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short);
  82.   return rep;
  83. }
  84.  
  85. BitSetRep* BitSetalloc(BitSetRep* old, const unsigned short* src, int srclen, 
  86.                 int newvirt, int newlen)
  87. {
  88.   if (old == &_nilBitSetRep) old = 0; 
  89.   BitSetRep* rep;
  90.   if (old == 0 || newlen >= old->sz)
  91.     rep = BSnew(newlen);
  92.   else
  93.     rep = old;
  94.  
  95.   rep->len = newlen;
  96.   rep->virt = newvirt;
  97.  
  98.   if (srclen != 0 && src != rep->s)
  99.     bcopy(src, rep->s, srclen * sizeof(short));
  100.  
  101.   if (old != rep && old != 0) delete old;
  102.   return rep;
  103. }
  104.  
  105. BitSetRep* BitSetresize(BitSetRep* old, int newlen)
  106. {
  107.   BitSetRep* rep;
  108.   if (old == 0 || old == &_nilBitSetRep)
  109.   {
  110.     rep = BSnew(newlen);
  111.     rep->virt = 0;
  112.   }
  113.   else if (newlen >= old->sz)
  114.   {
  115.     rep = BSnew(newlen);
  116.     bcopy(old->s, rep->s, old->len * sizeof(short));
  117.     rep->virt = old->virt;
  118.     delete old;
  119.   }
  120.   else
  121.     rep = old;
  122.  
  123.   rep->len = newlen;
  124.  
  125.   return rep;
  126. }
  127.  
  128. // same, for straight copy
  129.  
  130. BitSetRep* BitSetcopy(BitSetRep* old, const BitSetRep* src)
  131. {
  132.   BitSetRep* rep;
  133.   if (old == &_nilBitSetRep) old = 0;
  134.   if (src == 0 || src == &_nilBitSetRep)
  135.   {
  136.     if (old == 0)
  137.       rep = BSnew(0);
  138.     else
  139.       rep = old;
  140.     rep->len = 0;
  141.     rep->virt = 0;
  142.   }
  143.   else if (old == src) 
  144.     return old; 
  145.   else 
  146.   {
  147.     int newlen = src->len;
  148.     if (old == 0 || newlen > old->sz)
  149.     {
  150.       rep = BSnew(newlen);
  151.       if (old != 0) delete old;
  152.     }
  153.     else
  154.       rep = old;
  155.  
  156.     bcopy(src->s, rep->s, newlen * sizeof(short));
  157.     rep->len = newlen;
  158.     rep->virt = src->virt;
  159.   }
  160.   return rep;
  161. }
  162.  
  163.  
  164. // remove unneeded top bits
  165.  
  166. inline static void trim(BitSetRep* rep)
  167. {
  168.   int l = rep->len;
  169.   unsigned short* s = &(rep->s[l - 1]);
  170.  
  171.   if (rep->virt == 0)
  172.     while (l > 0 && *s-- == 0) --l;
  173.   else
  174.     while (l > 0 && *s-- == ONES) --l;
  175.   rep->len = l;
  176. }
  177.  
  178. int operator == (const BitSet& x, const BitSet& y)
  179. {
  180.   return x.rep->len == y.rep->len && x.rep->virt == y.rep->virt &&
  181.     bcmp((void*)x.rep->s, (void*)y.rep->s, 
  182.          x.rep->len * sizeof(short)) == 0;
  183. }
  184.  
  185.  
  186. int operator <= (const BitSet& x, const BitSet& y)
  187. {
  188.   if (x.rep->virt > y.rep->virt)
  189.     return 0;
  190.  
  191.   int xl = x.rep->len;
  192.   int yl = y.rep->len; 
  193.  
  194.   unsigned short* xs = x.rep->s;
  195.   unsigned short* ys = y.rep->s;
  196.   unsigned short* topx = &(xs[xl]);
  197.   unsigned short* topy = &(ys[yl]);
  198.  
  199.   while (xs < topx && ys < topy)
  200.   {
  201.     unsigned short a = *xs++;
  202.     unsigned short b = *ys++;
  203.     if ((a | b) != b)
  204.       return 0;
  205.   }
  206.   if (xl == yl)
  207.     return x.rep->virt <= y.rep->virt;
  208.   else if (xl < yl)
  209.     return !x.rep->virt;
  210.   else
  211.     return y.rep->virt;
  212. }
  213.  
  214.  
  215. int operator < (const BitSet& x, const BitSet& y)
  216. {
  217.   if (x.rep->virt > y.rep->virt)
  218.     return 0;
  219.  
  220.   int xl = x.rep->len;
  221.   int yl = y.rep->len;
  222.  
  223.   unsigned short* xs = x.rep->s;
  224.   unsigned short* ys = y.rep->s;
  225.   unsigned short* topx = &(xs[xl]);
  226.   unsigned short* topy = &(ys[yl]);
  227.   int one_diff = 0;
  228.   while (xs < topx && ys < topy)
  229.   {
  230.     unsigned short a = *xs++;
  231.     unsigned short b = *ys++;
  232.     unsigned short c = a | b;
  233.     if (c != b)
  234.       return 0;
  235.     else if (c != a)
  236.       one_diff = 1;
  237.   }
  238.   if (xl == yl)
  239.     return x.rep->virt < y.rep->virt || 
  240.       (one_diff && x.rep->virt == y.rep->virt);
  241.   else if (xl < yl)
  242.     return !x.rep->virt;
  243.   else
  244.     return y.rep->virt;
  245. }
  246.  
  247.  
  248.  
  249. int BitSet::empty() const
  250. {
  251.   if (rep->virt == 1)
  252.     return 0;
  253.  
  254.   unsigned short* bots = rep->s;
  255.   unsigned short* s = &(bots[rep->len - 1]);
  256.   while (s >= bots) if (*s-- != 0) return 0;
  257.   return 1;
  258. }
  259.  
  260.  
  261. int BitSet::count(int b) const
  262. {
  263.   if (b == rep->virt)
  264.     return -1;
  265.   int l = 0;
  266.   unsigned short* s = rep->s;
  267.   unsigned short* tops = &(s[rep->len]);
  268.   if (b == 1)
  269.   {
  270.     while (s < tops)
  271.     {
  272.       unsigned short a = *s++;
  273.       for (int i = 0; i < BITSETBITS && a != 0; ++i)
  274.       {
  275.         if (a & 1)
  276.           ++l;
  277.         a >>= 1;
  278.       }
  279.     }
  280.   }
  281.   else
  282.   {
  283.     unsigned short maxbit = 1 << (BITSETBITS - 1);
  284.     while (s < tops)
  285.     {
  286.       unsigned short a = *s++;
  287.       for (int i = 0; i < BITSETBITS; ++i)
  288.       {
  289.         if ((a & maxbit) == 0)
  290.           ++l;
  291.         a <<= 1;
  292.       }
  293.     }
  294.   }
  295.   return l;
  296. }
  297.  
  298. BitSetRep* BitSetcmpl(const BitSetRep* src, BitSetRep* r)
  299. {
  300.   r = BitSetcopy(r, src);
  301.   r->virt = !src->virt;
  302.   unsigned short* rs = r->s;
  303.   unsigned short* topr = &(rs[r->len]);
  304.   if (r->len == 0)
  305.     *rs = ONES;
  306.   else
  307.   {
  308.     while (rs < topr)
  309.     {
  310.       unsigned short cmp = ~(*rs);
  311.       *rs++ = cmp;
  312.     }
  313.   }
  314.   trim(r);
  315.   return r;
  316. }
  317.  
  318.  
  319. BitSetRep* BitSetop(const BitSetRep* x, const BitSetRep* y, 
  320.                     BitSetRep* r, char op)
  321. {
  322.   int xrsame = x == r;
  323.   int yrsame = y == r;
  324.   int xv = x->virt;
  325.   int yv = y->virt;
  326.   int xl = x->len;
  327.   int yl = y->len;
  328.   int rl = (xl >= yl)? xl : yl;
  329.  
  330.   r = BitSetresize(r, rl);
  331.   unsigned short* rs = r->s;
  332.   unsigned short* topr = &(rs[rl]);
  333.  
  334.   int av, bv;
  335.   const unsigned short* as;
  336.   const unsigned short* topa;
  337.   const unsigned short* bs;
  338.   const unsigned short* topb;
  339.   
  340.   if (xl <= yl)
  341.   {
  342.     as = (xrsame)? r->s : x->s;
  343.     av = xv;
  344.     topa = &(as[xl]);
  345.     bs = (yrsame)? r->s : y->s;
  346.     bv = yv;
  347.     topb = &(bs[yl]);
  348.   }
  349.   else
  350.   {
  351.     as = (yrsame)? r->s : y->s;
  352.     av = yv;
  353.     topa = &(as[yl]);
  354.     bs = (xrsame)? r->s : x->s;
  355.     bv = xv;
  356.     topb = &(bs[xl]);
  357.     if (op == '-')              // reverse sense of difference
  358.       op = 'D';
  359.   }
  360.  
  361.   switch (op)
  362.   {
  363.   case '&':
  364.     r->virt = av & bv;
  365.     while (as < topa) *rs++ = *as++ & *bs++;
  366.     if (av)
  367.       while (rs < topr) *rs++ = *bs++;
  368.     else
  369.       while (rs < topr) *rs++ = 0;
  370.     break;
  371.   case '|':
  372.     r->virt = av | bv;
  373.     while (as < topa) *rs++ = *as++ | *bs++;
  374.     if (av)
  375.       while (rs < topr) *rs++ = ONES;
  376.     else
  377.       while (rs < topr) *rs++ = *bs++;
  378.     break;
  379.   case '^':
  380.     r->virt = av ^ bv;
  381.     while (as < topa) *rs++ = *as++ ^ *bs++;
  382.     if (av)
  383.       while (rs < topr) *rs++ = ~(*bs++);
  384.     else
  385.       while (rs < topr) *rs++ = *bs++;
  386.     break;
  387.   case '-':
  388.     r->virt = av & ~(bv);
  389.     while (as < topa) *rs++ = *as++ & ~(*bs++);
  390.     if (av)
  391.       while (rs < topr) *rs++ = ~(*bs++);
  392.     else
  393.       while (rs < topr) *rs++ = 0;
  394.     break;
  395.   case 'D':
  396.     r->virt = ~(av) & (bv);
  397.     while (as < topa) *rs++ = ~(*as++) & (*bs++);
  398.     if (av)
  399.       while (rs < topr) *rs++ = 0;
  400.     else
  401.       while (rs < topr) *rs++ = *bs++;
  402.     break;
  403.   }
  404.   trim(r);
  405.   return r;
  406. }
  407.  
  408.  
  409. void BitSet::set(int p)
  410. {
  411.   if (p < 0) error("Illegal bit index");
  412.  
  413.   int index = BitSet_index(p);
  414.   int pos   = BitSet_pos(p);
  415.  
  416.   if (index >= rep->len)
  417.   {
  418.     if (rep->virt)
  419.       return;
  420.     else
  421.       rep = BitSetresize(rep, index+1);
  422.   }
  423.  
  424.   rep->s[index] |= (1 << pos);
  425. }
  426.  
  427. void BitSet::clear()
  428. {
  429.   if (rep->len > 0) bzero(rep->s, rep->sz * sizeof(short));
  430.   rep->len = rep->virt = 0;
  431. }
  432.  
  433. void BitSet::clear(int p)
  434. {
  435.   if (p < 0) error("Illegal bit index");
  436.   int index = BitSet_index(p);
  437.   if (index >= rep->len)
  438.   {
  439.     if (rep->virt == 0)
  440.       return;
  441.     else
  442.       rep = BitSetresize(rep, index+1);
  443.   }
  444.   rep->s[index] &= ~(1 << BitSet_pos(p));
  445. }
  446.  
  447. void BitSet::invert(int p)
  448. {
  449.   if (p < 0) error("Illegal bit index");
  450.   int index = BitSet_index(p);
  451.   if (index >= rep->len) rep = BitSetresize(rep, index+1);
  452.   rep->s[index] ^= (1 << BitSet_pos(p));
  453. }
  454.  
  455. void BitSet::set(int from, int to)
  456. {
  457.   if (from < 0 || from > to) error("Illegal bit index");
  458.  
  459.   int index1 = BitSet_index(from);
  460.   int pos1   = BitSet_pos(from);
  461.   
  462.   if (rep->virt && index1 >= rep->len)
  463.     return;
  464.  
  465.   int index2 = BitSet_index(to);
  466.   int pos2   = BitSet_pos(to);
  467.  
  468.   if (index2 >= rep->len)
  469.     rep = BitSetresize(rep, index2+1);
  470.  
  471.   unsigned short* s = &(rep->s[index1]);
  472.   unsigned short m1 = lmask(pos1);
  473.   unsigned short m2 = rmask(pos2);
  474.   if (index2 == index1)
  475.     *s |= m1 & m2;
  476.   else
  477.   {
  478.     *s++ |= m1;
  479.     unsigned short* top = &(rep->s[index2]);
  480.     *top |= m2;
  481.     while (s < top)
  482.       *s++ = ONES;
  483.   }
  484. }
  485.  
  486. void BitSet::clear(int from, int to)
  487. {
  488.   if (from < 0 || from > to) error("Illegal bit index");
  489.  
  490.   int index1 = BitSet_index(from);
  491.   int pos1   = BitSet_pos(from);
  492.   
  493.   if (!rep->virt && index1 >= rep->len)
  494.     return;
  495.  
  496.   int index2 = BitSet_index(to);
  497.   int pos2   = BitSet_pos(to);
  498.  
  499.   if (index2 >= rep->len)
  500.     rep = BitSetresize(rep, index2+1);
  501.  
  502.   unsigned short* s = &(rep->s[index1]);
  503.   unsigned short m1 = lmask(pos1);
  504.   unsigned short m2 = rmask(pos2);
  505.   if (index2 == index1)
  506.     *s &= ~(m1 & m2);
  507.   else
  508.   {
  509.     *s++ &= ~m1;
  510.     unsigned short* top = &(rep->s[index2]);
  511.     *top &= ~m2;
  512.     while (s < top)
  513.       *s++ = 0;
  514.   }
  515. }
  516.  
  517. void BitSet::invert(int from, int to)
  518. {
  519.   if (from < 0 || from > to) error("Illegal bit index");
  520.  
  521.   int index1 = BitSet_index(from);
  522.   int pos1   = BitSet_pos(from);
  523.   int index2 = BitSet_index(to);
  524.   int pos2   = BitSet_pos(to);
  525.  
  526.   if (index2 >= rep->len)
  527.     rep = BitSetresize(rep, index2+1);
  528.  
  529.   unsigned short* s = &(rep->s[index1]);
  530.   unsigned short m1 = lmask(pos1);
  531.   unsigned short m2 = rmask(pos2);
  532.   if (index2 == index1)
  533.     *s ^= m1 & m2;
  534.   else
  535.   {
  536.     *s++ ^= m1;
  537.     unsigned short* top = &(rep->s[index2]);
  538.     *top ^= m2;
  539.     while (s < top)
  540.     {
  541.       unsigned short cmp = ~(*s);
  542.       *s++ = cmp;
  543.     }
  544.   }
  545. }
  546.  
  547.  
  548. int BitSet::test(int from, int to) const
  549. {
  550.   if (from < 0 || from > to) return 0;
  551.  
  552.   int index1 = BitSet_index(from);
  553.   int pos1   = BitSet_pos(from);
  554.   
  555.   if (index1 >= rep->len)
  556.     return rep->virt;
  557.  
  558.   int index2 = BitSet_index(to);
  559.   int pos2   = BitSet_pos(to);
  560.  
  561.   if (index2 >= rep->len)
  562.   {
  563.     if (rep->virt)
  564.       return 1;
  565.     else 
  566.     {
  567.       index2 = rep->len - 1;
  568.       pos2 = BITSETBITS - 1;
  569.     }
  570.   }
  571.  
  572.   unsigned short* s = &(rep->s[index1]);
  573.   unsigned short m1 = lmask(pos1);
  574.   unsigned short m2 = rmask(pos2);
  575.  
  576.   if (index2 == index1)
  577.     return (*s & m1 & m2) != 0;
  578.   else
  579.   {
  580.     if (*s++ & m1)
  581.       return 1;
  582.     unsigned short* top = &(rep->s[index2]);
  583.     if (*top & m2)
  584.       return 1;
  585.     while (s < top)
  586.       if (*s++ != 0) 
  587.         return 1;
  588.     return 0;
  589.   }
  590. }
  591.  
  592. int BitSet::next(int p, int b) const
  593. {
  594.   ++p;
  595.   int index = BitSet_index(p);
  596.   int pos   = BitSet_pos(p);
  597.  
  598.   int l = rep->len;
  599.   
  600.   if (index >= l)
  601.   {
  602.     if (rep->virt == b)
  603.       return p;
  604.     else
  605.       return -1;
  606.   }
  607.   int j = index;
  608.   unsigned short* s = rep->s;
  609.   unsigned short a = s[j] >> pos;
  610.   int i = pos;
  611.  
  612.   if (b == 1)
  613.   {
  614.     for (; i < BITSETBITS && a != 0; ++i)
  615.     {
  616.       if (a & 1)
  617.         return j * BITSETBITS + i;
  618.       a >>= 1;
  619.     }
  620.     for (++j; j < l; ++j)
  621.     {
  622.       a = s[j];
  623.       for (i = 0; i < BITSETBITS && a != 0; ++i)
  624.       {
  625.         if (a & 1)
  626.           return j * BITSETBITS + i;
  627.         a >>= 1;
  628.       }
  629.     }
  630.     if (rep->virt)
  631.       return j * BITSETBITS;
  632.     else
  633.       return -1;
  634.   }
  635.   else
  636.   {
  637.     for (; i < BITSETBITS; ++i)
  638.     {
  639.       if ((a & 1) == 0)
  640.         return j * BITSETBITS + i;
  641.       a >>= 1;
  642.     }
  643.     for (++j; j < l; ++j)
  644.     {
  645.       a = s[j];
  646.       if (a != ONES)
  647.       {
  648.         for (i = 0; i < BITSETBITS; ++i)
  649.         {
  650.           if ((a & 1) == 0)
  651.             return j * BITSETBITS + i;
  652.           a >>= 1;
  653.         }
  654.       }
  655.     }
  656.     if (!rep->virt)
  657.       return j * BITSETBITS;
  658.     else
  659.       return -1;
  660.   }
  661. }
  662.  
  663. int BitSet::previous(int p, int b) const
  664. {
  665.   if (--p < 0)
  666.     return -1;
  667.  
  668.   int index = BitSet_index(p);
  669.   int pos   = BitSet_pos(p);
  670.  
  671.   unsigned short* s = rep->s;
  672.   int l = rep->len;
  673.  
  674.   if (index >= l)
  675.   {
  676.     if (rep->virt == b)
  677.       return p;
  678.     else
  679.     {
  680.       index = l - 1;
  681.       pos = BITSETBITS - 1;
  682.     }
  683.   }
  684.  
  685.   int j = index;
  686.   unsigned short a = s[j];
  687.  
  688.   int i = pos;
  689.   unsigned short maxbit = 1 << pos;
  690.  
  691.   if (b == 1)
  692.   {
  693.     for (; i >= 0 && a != 0; --i)
  694.     {
  695.       if (a & maxbit)
  696.         return j * BITSETBITS + i;
  697.       a <<= 1;
  698.     }
  699.     maxbit = 1 << (BITSETBITS - 1);
  700.     for (--j; j >= 0; --j)
  701.     {
  702.       a = s[j];
  703.       for (i = BITSETBITS - 1; i >= 0 && a != 0; --i)
  704.       {
  705.         if (a & maxbit)
  706.           return j * BITSETBITS + i;
  707.         a <<= 1;
  708.       }
  709.     }
  710.     return -1;
  711.   }
  712.   else
  713.   {
  714.     if (a != ONES)
  715.     {
  716.       for (; i >= 0; --i)
  717.       {
  718.         if ((a & maxbit) == 0)
  719.           return j * BITSETBITS + i;
  720.         a <<= 1;
  721.       }
  722.     }
  723.     maxbit = 1 << (BITSETBITS - 1);
  724.     for (--j; j >= 0; --j)
  725.     {
  726.       a = s[j];
  727.       if (a != ONES)
  728.       {
  729.         for (i = BITSETBITS - 1; i >= 0; --i)
  730.         {
  731.           if ((a & maxbit) == 0)
  732.             return j * BITSETBITS + i;
  733.           a <<= 1;
  734.         }
  735.       }
  736.     }
  737.     return -1;
  738.   }
  739. }
  740.  
  741. int BitSet::last(int b) const
  742. {
  743.   if (b == rep->virt)
  744.     return -1;
  745.   else
  746.     return previous((rep->len) * BITSETBITS, b);
  747. }
  748.  
  749.  
  750. extern AllocRing _libgxx_fmtq;
  751.  
  752. const char* BitSettoa(const BitSet& x, char f, char t, char star)
  753. {
  754.   trim(x.rep);
  755.  
  756.   int wrksiz = (x.rep->len + 1) * BITSETBITS + 2;
  757.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  758.   char* fmt = fmtbase;
  759.  
  760.   const unsigned short* s = x.rep->s;
  761.   const unsigned short* top = &(s[x.rep->len - 1]);
  762.  
  763.   while (s < top)
  764.   {
  765.     unsigned short a = *s++;
  766.     for (int j = 0; j < BITSETBITS; ++j)
  767.     {
  768.       *fmt++ = (a & 1)? t : f;
  769.       a >>= 1;
  770.     }
  771.   }
  772.  
  773.   if (!x.rep->virt)
  774.   {
  775.     unsigned short a = *s;
  776.     if (x.rep->len != 0)
  777.     {
  778.       for (int j = 0; j < BITSETBITS && a != 0; ++j)
  779.       {
  780.         *fmt++ = (a & 1)? t : f;
  781.         a >>= 1;
  782.       }
  783.     }
  784.     *fmt++ = f;
  785.   }
  786.   else
  787.   {
  788.     unsigned short a = *s;
  789.     unsigned short mask = ONES;
  790.     unsigned short himask = (1 << (BITSETBITS - 1)) - 1;
  791.     if (x.rep->len != 0)
  792.     {
  793.       for (int j = 0; j < BITSETBITS && a != mask; ++j)
  794.       {
  795.         *fmt++ = (a & 1)? t : f;
  796.         a = (a >> 1) & himask;
  797.         mask = (mask >> 1) & himask;
  798.       }
  799.     }
  800.     *fmt++ = t;
  801.   }
  802.  
  803.   *fmt++ = star;
  804.   *fmt++ = 0;
  805.   return fmtbase;
  806. }
  807.  
  808. #if defined(__GNUG__) && !defined(NO_NRV)
  809.  
  810. BitSet shorttoBitSet(unsigned short w) return r
  811. {
  812.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  813. }
  814.  
  815. BitSet longtoBitSet(unsigned long w) return r;
  816. {
  817.   unsigned short u[2];
  818.   u[0] = w & ((unsigned short)(~(0)));
  819.   u[1] = w >> BITSETBITS;
  820.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  821.   trim(r.rep);
  822. }
  823.  
  824. BitSet atoBitSet(const char* s, char f, char t, char star) return r
  825. {
  826.   int sl = strlen(s);
  827.   if (sl != 0)
  828.   {
  829.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  830.     unsigned short* rs = r.rep->s;
  831.     unsigned short a = 0;
  832.     unsigned short m = 1;
  833.     char lastch = 0;
  834.     unsigned int i = 0;
  835.     unsigned int l = 1;
  836.     for(;;)
  837.     {
  838.       char ch = s[i];
  839.       if (ch == t)
  840.         a |= m;
  841.       else if (ch == star)
  842.       {
  843.         if (r.rep->virt = lastch == t)
  844.           *rs = a | ~(m - 1);
  845.         else
  846.           *rs = a;
  847.         break;
  848.       }
  849.       else if (ch != f)
  850.       {
  851.         *rs = a;
  852.         break;
  853.       }
  854.       lastch = ch;
  855.       if (++i == sl)
  856.       {
  857.         *rs = a;
  858.         break;
  859.       }
  860.       else if (i % BITSETBITS == 0)
  861.       {
  862.         *rs++ = a;
  863.         a = 0;
  864.         m = 1;
  865.         ++l;
  866.       }
  867.       else
  868.         m <<= 1;
  869.     }
  870.     r.rep->len = l;
  871.     trim(r.rep);
  872.   }
  873.   return;
  874. }
  875.  
  876. #else
  877.  
  878. BitSet shorttoBitSet(unsigned short w) 
  879. {
  880.   BitSet r;
  881.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  882.   return r;
  883. }
  884.  
  885. BitSet longtoBitSet(unsigned long w)
  886. {
  887.   BitSet r;
  888.   unsigned short u[2];
  889.   u[0] = w & ((unsigned short)(~(0)));
  890.   u[1] = w >> BITSETBITS;
  891.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  892.   trim(r.rep);
  893.   return r;
  894. }
  895.  
  896. BitSet atoBitSet(const char* s, char f, char t, char star) 
  897. {
  898.   BitSet r;
  899.   int sl = strlen(s);
  900.   if (sl != 0)
  901.   {
  902.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  903.     unsigned short* rs = r.rep->s;
  904.     unsigned short a = 0;
  905.     unsigned short m = 1;
  906.     char lastch = 0;
  907.     unsigned int i = 0;
  908.     unsigned int l = 1;
  909.     for(;;)
  910.     {
  911.       char ch = s[i];
  912.       if (ch == t)
  913.         a |= m;
  914.       else if (ch == star)
  915.       {
  916.         if (r.rep->virt = lastch == t)
  917.           *rs = a | ~(m - 1);
  918.         else
  919.           *rs = a;
  920.         break;
  921.       }
  922.       else if (ch != f)
  923.       {
  924.         *rs = a;
  925.         break;
  926.       }
  927.       lastch = ch;
  928.       if (++i == sl)
  929.       {
  930.         *rs = a;
  931.         break;
  932.       }
  933.       else if (i % BITSETBITS == 0)
  934.       {
  935.         *rs++ = a;
  936.         a = 0;
  937.         m = 1;
  938.         ++l;
  939.       }
  940.       else
  941.         m <<= 1;
  942.     }
  943.     r.rep->len = l;
  944.     trim(r.rep);
  945.   }
  946.   return r;
  947. }
  948.  
  949. #endif
  950.  
  951. ostream& operator << (ostream& s, const BitSet& x)
  952. {
  953.   return s << BitSettoa(x);
  954. }
  955.  
  956. int BitSet::OK() const
  957. {
  958.   int v = rep != 0;             // have a rep
  959.   v &= rep->len <= rep->sz;     // within bounds
  960.   v &= rep->virt == 0 || rep->virt == 1; // valid virtual bit
  961.   if (!v) error("invariant failure");
  962.   return v;
  963. }
  964.  
  965.